package dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 44. 通配符匹配
 */
public class P44 {
    public boolean isMatch(String s, String p) {
        p = p.replaceAll("\\*+", "*");
        if (p.equals("*")) {
            return true;
        }


        //匹配
        int p1 = 0, p2 = 0;
        while (p1 < s.length() && p2 < p.length()) {
            char c1 = s.charAt(p1);
            char c2 = p.charAt(p2);
            if (c1 == c2) {
                p1++;
                p2++;
            } else if (c2 == '?') {
                p1++;
                p2++;
            } else if (c2 == '*') {
                if (p2 == p.length() - 1 && p1 == s.length() - 1) {
                    return true;
                }
                //
                List<Integer> idxList = getValidIdx(s.substring(p1), p.charAt(p2 + 1));
                for (int idx : idxList) {
                    if (isMatch(s.substring(p1 + idx), p.substring(p2 + 1))) {
                        return true;
                    }
                }
                return false;
            } else {
                return false;
            }
        }
        while (p2 < p.length() && p.charAt(p2) == '*') {
            p2++;
        }
        return p1 == s.length() && p2 == p.length() ? true : false;
    }

    private List<Integer> getValidIdx(String s, char c) {
        List<Integer> idxList = new ArrayList<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (c == chars[i] || c=='?') {
                idxList.add(i);
            }
        }
        return idxList;
    }

    public static void main(String[] args) {
        boolean flag = new P44().isMatch("c", "*?*");
        System.out.println(flag);
    }
}
